2024牛客暑期多校训练营6 题解

A - Cake

Question

两个人玩游戏，游戏分两阶段

第一阶段在一棵有根树上轮流走，走到叶子停止，有根树边上有 $01$ 标记，记录下走过的 $01$ 串（Grammy 先走）

第二阶段分蛋糕，Oscar 按自己的意愿切蛋糕，然后按照第一阶段获得的 $01$ 串顺序依次拿蛋糕（ $1$ 代表 Grammy 拿， $0$ 代表 Oscar 拿）

两人都想让自己获得尽量多的蛋糕，求最后 Grammy 获得的蛋糕比例

$2 \leq n \leq 2 \times 10^{5}$

Solution

首先考虑第二阶段，Oscar 的最优方案是选择一个 $0$ 占比最大的前缀 $L$ ，将蛋糕切成 $L$ 个 $\frac{1}{L}$ 大小的块，然后自己拿走 $0$ 的占比那么多

所以对于第一阶段，Oscar 的目标是经过前缀 $0$ 占比尽量大的点，Grammy 的目标是经过前缀 $0$ 占比尽量小的点

具体怎么 DP，定义 $f [u]$ 表示从起点到 $u$ 节点的 $01$ 串中， $0$ 占比最大的前缀的比例，这个可以用一个从父节点到子节点的 dfs 来解决

然后定义 $d p [u]$ 表示走到 $u$ ，现在要走这个人按照最优走法的最大前缀 $0$ 的占比，显然，当 $u$ 没有叶子节点时， $d p [u] = f [u]$ ，然后我们可以按照深度来算出当前这个节点时谁走，如果是 Oscar 走，那么他肯定往最大的 $d p [v]$ 走，如果是 Grammy 走，那么他肯定往最小的 $d p [v]$ 走，这个可以用一个从叶子到根节点的 DP 来解决

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w}); g[v].push_back({u, w});
    }
    vector<int> dep(n + 1); dep[1] = 1;
    vector<double> f(n + 1); f[1] = 0; // f 表示前缀 0 的最大占比
    vector<array<int, 2>> cnt(n + 1); cnt[0] = {0, 0}; 

    function<void(int, int)> dfs1 = [&] (int u, int fa) {
        if (u != 1) 
            f[u] = max(1.0 * f[u], 1.0 * cnt[u][0] / (cnt[u][0] + cnt[u][1]));
        for (auto [v , w] : g[u]) {
            if (v == fa) continue;
            dep[v] = dep[u] + 1;
            cnt[v] = cnt[u]; cnt[v][w] += 1;
            f[v] = f[u];
            dfs1 (v, u);
        }
    };

    vector<double> dp(n + 1); // dp 表示走到 u 的最优解
    function<void(int, int)> dfs2 = [&] (int u, int fa) {
        if (dep[u] & 1) dp[u] = 1;
        else dp[u] = 0;
        int flg = 0;
        for (auto [v, w] : g[u]) {
            if (v == fa) continue;
            dfs2(v, u);
            flg = 1;
            if (dep[u] & 1) dp[u] = min(dp[u], dp[v]);
            else dp[u] = max(dp[u], dp[v]);
        }
        if (!flg) dp[u] = f[u];
    };

    dfs1(1, 0);
    dfs2(1, 0);
    cout << fixed << setprecision(10) << 1 - dp[1] << '\n';
}

int main() {
    freopen ("A.in", "r", stdin);
    ios::sync_with_stdio(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

B - Cake 2

Solution

自己多花几个，然后就能找到规律， $a n s = n \times min (k, n - k) + 1$

当然要特别考虑 $2 k = n$ 的情况

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long N, K; cin >> N >> K;
    if (N % 2 == 0 && K == N / 2) {
        cout << N << endl;
    }
    else if (K > N / 2) {
        K = N - K;
        cout << N * K + 1 << endl;
    }
    else {
        cout << N * K + 1 << endl;
    }
    return 0;
}

D - Puzzle: Wagiri

Question

给定一张简单连通无向图，边有黑白，移除任意多条边使得图仍然连通，且黑边都在环上，白边都不在环上，或输出无解

$1 < n \leq 10^{5}$

Solution

保留所有黑边，做边双连通分量

然后去掉所有桥边，使用白边将原本不连通的连通块连起来，就是做一个 MST

如果最终得到的图连通，则已经获得了一个解，否则无解

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n + 1);
    map<pii, int> mp, mp2;
    for (int i = 1; i <= m; i++) {
        string s; int u, v, w; cin >> u >> v; cin >> s;
        w = (s == "Lun");
        if (w == 1) {
            mp[{u, v}] = 1;
            g[u].push_back(v); g[v].push_back(u);
        }
        else {
            mp2[{u, v}] = 1;
        }
    }
    
    vector<int> dfn(n + 1, 0), low(n + 1, 0); int dfn_cnt = 0;
    vector<pair<int, int>> cut_bridge;

    function<void(int, int)> tarjan = [&] (int u, int fa) {
        dfn[u] = low[u] = ++dfn_cnt;
        for (auto v : g[u]) {
            if (!dfn[v]) {
                tarjan(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) cut_bridge.push_back({u, v});
            }
            else if (v != fa) low[u] = min(low[u], dfn[v]);
        }
    };

    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);
    for (auto [u, v] : cut_bridge) {
        mp.erase({u, v}); mp.erase({v, u});
    }

    vector<int> fa(n + 1);
    iota(fa.begin(), fa.end(), 0);

    function<int(int)> find = [&] (int x) -> int {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    };

    for (auto [x, _] : mp) {
        auto [u, v] = x;
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;
        fa[fu] = fv;
    }

    for (auto [x, _] : mp2) {
        auto [u, v] = x;
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;
        fa[fu] = fv;
        mp[{u, v}] = 1;
    }

    vector<int> hsh(n + 1, 0);
    for (int i = 1; i <= n; i++) hsh[find(i)]++;
    int cnt = 0;
    for (int i = 1; i <= n; i++) cnt += (hsh[i] > 0);
    if (cnt > 1) { cout << "NO" << endl; return 0;}

    cout << "YES" << '\n';
    cout << mp.size() << '\n';
    for (auto [u, v] : mp) {
        cout << u.first << ' ' << u.second << '\n';
    }
    return 0;
}

F - Challenge NPC 2

Question

给定一颗森林，求其补图的哈夫曼路径

$n \leq 5 \times 10^{5}$

Solution

考虑到一层中的点在原图中是没有边的，说明其在补图中是有边的，所以对于一层的节点，是可以一串处理掉的

然后考虑如何链接不同层，很容易想到的方法就是奇偶链接： $1 \to 3 \to 5, 2 \to 4 \to 6$ ，然后把 $4$ 和 $1$ 连，这样子就全部串在一起了

考虑无解的情况，就是一个菊花图

如果最深的深度小于 $4$

如果为 $1$ 说明都是单点，串起来即可
如果为 $2$ ，如果只有一颗树无解，如果有多棵树，则分层串
如果为 $3$ ，还是奇偶分层，然后找一个 $d e p [x] = 2, d e p [y] = 3$ 且 $x, y$ 直接没有连边的 $x, y$ ，把他们在补图中作为哈夫曼路径即可

具体实现还是挺恶心的

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m; cin >> n >> m;
    vector<int> dep(n + 1, 0), rt(n + 1, 0);
    vector<vector<int>> g(n + 1);

    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }

    vector<int> root;

    function<void(int, int, int, int)> dfs = [&](int u, int fa, int d, int r) {
        dep[u] = d; rt[u] = r;
        for (auto v : g[u]) {
            if (v == fa) continue;
            dfs(v, u, d + 1, r);
        }
    };

    for (int i = 1; i <= n; i++) {
        if (dep[i] != 0) continue;
        root.push_back(i);
        dfs(i, 0, 1, i);
    }

    int max_dep = *max_element(dep.begin() + 1, dep.end()); // max_dep 表示最深的深度
    
    if (max_dep == 1) {
        for (int i = 1; i <= n; i++) cout << i << ' ';
        cout << '\n';
        return ;
    }
    if (root.size() > 1) {
        int x, y;
        for (int i = 1; i <= n; i++) if (dep[i] == 2) x = i;
        for (int i = 1; i <= n; i++) if (dep[i] == 1 && rt[i] != rt[x]) y = i;
        for (int i = 1; i <= n; i++) if ((dep[i] & 1) && i != y) cout << i << ' ';
        cout << y << ' ' << x << ' ';
        for (int i = 1; i <= n; i++) if ((dep[i] & 1) == 0 && i != x) cout << i << ' ';
        cout << '\n';
    }
    else  {
        if (max_dep == 2) {
            cout << "-1" << '\n';
        }
        else if (max_dep == 3) {
            int x, y;
            vector<int> v;
            for (int i = 1; i <= n; i++) if (dep[i] == 2) v.push_back(i);
            if (v.size() == 1) {
                cout << "-1" << '\n';
            }else {
                int x, y;
                for (int i = 1; i <= n; i++) if (dep[i] == 3) y = i;
                for (auto u : v) {
                    bool flg = 1;
                    for (auto v : g[u]) {
                        if (v == y) {flg = 0; break;}
                    }
                    if (flg) {x = u; break;}
                }
                for (int i = 1; i <= n; i++) if ((dep[i] & 1) && i != y) cout << i << ' ';
                cout << y << ' ' << x << ' ';
                for (int i = 1; i <= n; i++) if ((dep[i] & 1) == 0 && i != x) cout << i << ' ';
                cout << '\n';
            }
        }
        else {
            int x, y;
            for (int i = 1; i <= n; i++) {
                if (dep[i] == 1) x = i;
                if (dep[i] == 4) y = i; 
            }
            for (int i = 1; i <= n; i++) if ((dep[i] & 1) && i != y) cout << i << ' ';
            cout << y << ' ' << x << ' ';
            for (int i = 1; i <= n; i++) if ((dep[i] & 1) == 0 && i != x) cout << i << ' ';
            cout << '\n';
        }
    }
} 

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

H - Genshin Impact's Fault

Solution

签到题

Code

#include <bits/stdc++.h>
using namespace std;

bool check1 (string s) {
    int n = s.size(); s = " " + s;
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + (s[i] == '3');
    for (int l = 1; l + 10 - 1 <= n; l++) {
        int r = l + 10 - 1;
        if (sum[r] - sum[l - 1] == 10) return false;
    }
    return true;
}

bool check2(string s) {
    int n = s.size(); s = " " + s;
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '5' || s[i] == 'U') sum[i] = sum[i - 1] + 1;
        else sum[i] = sum[i - 1];
    }
    for (int l = 1; l + 90 - 1 <= n; l++) {
        int r = l + 90 - 1;
        if (sum[r] - sum[l - 1] == 0) return false;
    }
    return true;
}

bool check3 (string s) {
    char lst = ' ';
    for (auto ch: s) {
        if (ch == 'U' || ch == '5') {
            if (lst == '5' && ch == '5') return false;
            lst = ch;
        }
    }
    return true;
}

void solve() {
    string s; cin >> s;
    bool res = check1(s) && check2(s) && check3(s);
    cout << (res ? "valid" : "invalid") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

I - Intersecting Intervals

Question

给定一个数字矩阵，每一行选择一个区间，要求相邻行的区间有交，求最大化选中的数字和

Solution

有点类似于最大子段求和，但是这里是多行的

定义 $d p [i] [j]$ 表示前 $i$ 行，强制选择 $a [i] [j]$ 的最优答案

那么转移就需要枚举上一行选择的数字 $k$ 并且保证上一行和这一行有交

那么转移方程就是

d p [i] [j] = {\begin{cases} max d p [i - 1] [k] + \sum_{p = k}^{j} a [i] [p] + p r e [k - 1] + s u f [i + 1], k \leq j \\ max d p [i - 1] [k] + \sum_{p = j}^{k} a [i] [p] + p r e [i - 1] + s u f [k + 1], k > j \end{cases}

其中 $p r e [i]$ 表示以 $i$ 结尾的最长子序列大小， $s u f [i]$ 表示以 $i$ 开头的最长子序列大小

此时的转移是 $O (n m^{2})$ ，但是这里可以使用前缀/后缀 $max$ 优化转移，时间复杂度为 $O (n m)$

具体实现就是定义一个数组 $p r e 2 [j]$ 表示 $max {d p [i - 1] [k] + \sum_{p = k}^{j} a [i] [p] + p r e [k - 1]}, k \leq j$

那么对于 $p r e 2 [j]$ 的转移就是 $max {p r e 2 [j - 1] + a [i] [j], p r e [j] + d p [i - 1] [j]}$ ， $s u f 2$ 也是同理

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<ll>> a(n + 5, vector<ll>(m + 5, 0));
    vector<vector<ll>> dp(n + 5, vector<ll>(m + 5, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    for (int i = 1; i <= n; i++) {
        vector<ll> pre(m + 5, 0), pre_max(m + 5, 0), suf(m + 5, 0), suf_max(m + 5, 0);
        for (int j = 1; j <= m; j++) {
            pre[j] = max(pre[j - 1] + a[i][j], a[i][j]);
            if(j == 1) pre_max[j] = pre[j] + dp[i - 1][j];
            else pre_max[j] = max(pre_max[j - 1] + a[i][j], pre[j] + dp[i - 1][j]);
        }
        for (int j = m; j >= 1; j--) {
            suf[j] = max(suf[j + 1] + a[i][j], a[i][j]);
            if(j == m) suf_max[j] = suf[j] + dp[i - 1][j];
            else suf_max[j] = max(suf_max[j + 1] + a[i][j], suf[j] + dp[i - 1][j]);
        }
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(pre[j] + suf_max[j], pre_max[j] + suf[j]) - a[i][j];
        }
    }
    ll ans = *max_element(dp[n].begin() + 1, dp[n].end());
    cout << ans << '\n';
}

int main() {
    freopen ("I.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}